<!DOCTYPE html>

<html lang="zh-CN">

<head>
  
  <title>线性表 - lingqu&#39;blog</title>
  <meta charset="UTF-8">
  <meta name="description" content="">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=5">
  
  

  <link rel="shortcut icon" href="/favicon.ico" type="image/png" />
  <meta name="description" content="线性表：由同类型数据元素构成有序序列的线性结构  表中元素个数称为线性表的长度 没有元素时，称为空表 起始位置称表头，表结束位置称表尾">
<meta property="og:type" content="article">
<meta property="og:title" content="线性表">
<meta property="og:url" content="https://lingqu.github.io/2021/05/16/linearList/index.html">
<meta property="og:site_name" content="lingqu&#39;blog">
<meta property="og:description" content="线性表：由同类型数据元素构成有序序列的线性结构  表中元素个数称为线性表的长度 没有元素时，称为空表 起始位置称表头，表结束位置称表尾">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://lingqu.github.io/2021/05/16/linearList/Snipaste_2021-05-15_15-38-27.png">
<meta property="og:image" content="https://lingqu.github.io/2021/05/16/linearList/Snipaste_2021-05-14_20-41-25.png">
<meta property="og:image" content="https://lingqu.github.io/2021/05/16/linearList/Snipaste_2021-05-14_22-52-16.png">
<meta property="article:published_time" content="2021-05-16T11:02:59.000Z">
<meta property="article:modified_time" content="2021-05-27T14:23:44.842Z">
<meta property="article:author" content="lingqu">
<meta property="article:tag" content="数据结构">
<meta property="article:tag" content="C++">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://lingqu.github.io/2021/05/16/linearList/Snipaste_2021-05-15_15-38-27.png">
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/combine/npm/highlight.js@9.15.8/styles/atom-one-dark.css,npm/justifiedGallery@3.8.1/dist/css/justifiedGallery.min.css,gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css,npm/hexo-theme-nexmoe@latest/source/lib/mdui_043tiny/css/mdui.css,npm/hexo-theme-nexmoe@latest/source/lib/iconfont/iconfont.css?v=233" crossorigin>
  <link rel="stylesheet" href="/css/style.css?v=1629344957177">
  
  <link rel="stylesheet" href="/css/style.css?v=1629344957177">
  <link rel="stylesheet" href="/lib/iconfont/iconfont.css?v=1629344957177">
<meta name="generator" content="Hexo 5.4.0"></head>

<body class="mdui-drawer-body-left">
  
  <div id="nexmoe-background">
    <div class="nexmoe-bg" style="background-image: url(http://pic1.win4000.com/wallpaper/f/5922779a761cd.jpg)"></div>
    <div class="mdui-appbar mdui-shadow-0">
      <div class="mdui-toolbar">
        <a mdui-drawer="{target: '#drawer', swipe: true}" title="menu" class="mdui-btn mdui-btn-icon mdui-ripple"><i class="mdui-icon nexmoefont icon-menu"></i></a>
        <div class="mdui-toolbar-spacer"></div>
        <!--<a href="javascript:;" class="mdui-btn mdui-btn-icon"><i class="mdui-icon material-icons">search</i></a>-->
        <a href="/" title="lingqu" class="mdui-btn mdui-btn-icon"><img src="https://inews.gtimg.com/newsapp_bt/0/13492515314/1000" alt="lingqu"></a>
       </div>
    </div>
  </div>
  <div id="nexmoe-header">
      <div class="nexmoe-drawer mdui-drawer" id="drawer">
    <div class="nexmoe-avatar mdui-ripple">
        <a href="/" title="lingqu">
            <img src="https://inews.gtimg.com/newsapp_bt/0/13492515314/1000" alt="lingqu" alt="lingqu">
        </a>
    </div>
    <div class="nexmoe-count">
        <div><span>文章</span>8</div>
        <div><span>标签</span>3</div>
        <div><span>分类</span>0</div>
    </div>
    <div class="nexmoe-list mdui-list" mdui-collapse="{accordion: true}">
        
        <a class="nexmoe-list-item mdui-list-item mdui-ripple" href="/" title="回到首页">
            <i class="mdui-list-item-icon nexmoefont icon-home"></i>
            <div class="mdui-list-item-content">
                回到首页
            </div>
        </a>
        
        <a class="nexmoe-list-item mdui-list-item mdui-ripple" href="/about.html" title="关于博客">
            <i class="mdui-list-item-icon nexmoefont icon-info-circle"></i>
            <div class="mdui-list-item-content">
                关于博客
            </div>
        </a>
        
        <a class="nexmoe-list-item mdui-list-item mdui-ripple" href="/PY.html" title="我的朋友">
            <i class="mdui-list-item-icon nexmoefont icon-unorderedlist"></i>
            <div class="mdui-list-item-content">
                我的朋友
            </div>
        </a>
        
    </div>
    <aside id="nexmoe-sidebar">
  
  <div class="nexmoe-widget-wrap">
    <div class="nexmoe-widget nexmoe-search">
        <form id="search_form" action_e="https://cn.bing.com/search?q=site:nexmoe.com" onsubmit="return search();">
            <label><input id="search_value" name="q" type="search" placeholder="搜索"></label>
        </form>
    </div>
</div>
  
  <div class="nexmoe-widget-wrap">
    <div class="nexmoe-widget nexmoe-social">
        <a class="mdui-ripple" href="https://jq.qq.com/?_wv=1027&k=5CfKHun" target="_blank" mdui-tooltip="{content: 'QQ群'}" style="color: rgb(249, 174, 8);background-color: rgba(249, 174, 8, .1);">
            <i class="nexmoefont icon-QQ"></i>
        </a><a class="mdui-ripple" href="https://space.bilibili.com/51207190" target="_blank" mdui-tooltip="{content: '哔哩哔哩'}" style="color: rgb(231, 106, 141);background-color: rgba(231, 106, 141, .15);">
            <i class="nexmoefont icon-bilibili"></i>
        </a><a class="mdui-ripple" href="https://github.com/lingqu/" target="_blank" mdui-tooltip="{content: 'GitHub'}" style="color: rgb(25, 23, 23);background-color: rgba(25, 23, 23, .15);">
            <i class="nexmoefont icon-github"></i>
        </a>
    </div>
</div>
  
  

  
  
  <div class="nexmoe-widget-wrap">
    <div id="randomtagcloud" class="nexmoe-widget tagcloud nexmoe-rainbow">
      <a href="/tags/C/" style="font-size: 20px;">C++</a> <a href="/tags/JavaScript/" style="font-size: 10px;">JavaScript</a> <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="font-size: 20px;">数据结构</a>
    </div>
    
  </div>

  
</aside>
    <div class="nexmoe-copyright">
        &copy; 2021 lingqu
        Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
        & <a href="https://github.com/theme-nexmoe/hexo-theme-nexmoe" target="_blank">Nexmoe</a>
        
    </div>
</div><!-- .nexmoe-drawer -->
  </div>
  <div id="nexmoe-content">
    <div class="nexmoe-primary">
        <div class="nexmoe-post">

  <article>
    
        <div class="nexmoe-post-cover" style="padding-bottom: 45.83333333333333%;"> 
            <img data-src="http://pic1.win4000.com/wallpaper/f/5922779a761cd.jpg" data-sizes="auto" alt="线性表" class="lazyload">
            <h1>线性表</h1>
        </div>
    
    
    <div class="nexmoe-post-meta nexmoe-rainbow" style="margin:10px 0!important;">
    <a><i class="nexmoefont icon-calendar-fill"></i>2021年05月16日</a>
    <a><i class="nexmoefont icon-areachart"></i>1,497 字</a>
    <a><i class="nexmoefont icon-time-circle-fill"></i>大概 7 分钟</a>
</div>

    

    <p>线性表：由同类型数据元素构成有序序列的线性结构</p>
<ul>
<li>表中元素个数称为线性表的长度</li>
<li>没有元素时，称为空表</li>
<li>起始位置称表头，表结束位置称表尾<span id="more"></span>
<h2 id="数组"><a href="#数组" class="headerlink" title="数组"></a>数组</h2><h3 id="存储"><a href="#存储" class="headerlink" title="存储"></a>存储</h3></li>
</ul>
<p>利用数组的连续空间顺序存放线性表的各元素</p>
<p><img data-fancybox="gallery" data-sizes="auto" data-src="Snipaste_2021-05-15_15-38-27.png" alt="art" class="lazyload"></p>
<pre><code class="c++">typedef struct LNode *List;
struct LNode&#123;
    ElementType Data[MAXSIZE];
    int Last;
&#125;;
struct LNode L;
List PtrL;
//访问数据：L.Data[i]或PtrL-&gt;Data[i]
//线性表的长度：L.Last+1或PtrL-&gt;Last+1
</code></pre>
<h3 id="主要操作"><a href="#主要操作" class="headerlink" title="主要操作"></a>主要操作</h3><h4 id="初始化"><a href="#初始化" class="headerlink" title="初始化"></a>初始化</h4><p>（建立空的顺序表）</p>
<pre><code class="c++">List MakeEmpty()&#123;
    List PtrL;
    PtrL = (List) new LNode;
    PtrL-&gt;Last=-1;
    return PtrL;
&#125;
</code></pre>
<h4 id="查找"><a href="#查找" class="headerlink" title="查找"></a>查找</h4><pre><code class="c++">int Find(ElementType X,LIst PtrL)
&#123;
    int i=0;
    while(i&lt;Ptrl-&gt;Last &amp;&amp; PtrL-&gt;data[i]!=X)
        i++;
    if(i&gt;PtrL-&gt;Last)  return -1;
    else return i;
&#125;
</code></pre>
<h4 id="插入"><a href="#插入" class="headerlink" title="插入"></a>插入</h4><p>(第i(1&lt;=i&lt;=n+1)个位置上插入一个值为X新元素)</p>
<p>因为下标是从0开始，所以实际上需要把i-1及以后的所以元素都向后移动一位再在i-1位置放入新元素</p>
<pre><code class="c++">void insert(ElementType X,int i,List PtrL)
&#123;
    //判断表是否满和插入的位置是否合法
    if(PtrL-&gt;Last==MAXSIZE)&#123;
        cout&lt;&lt;&quot;表满&quot;;
        return;
    &#125;
    if(i&lt;1 || i &gt; PtrL-&gt;Last+2)&#123;
        cout&lt;&lt;&quot;位置不合法&quot;;
        return;
    &#125;
    //移动i-1及以后的元素
    for(int j=PtrL-&gt;Last;j&gt;=i-1;j--)&#123;
        PtrL-&gt;Data[j+1]=PtrL-&gt;Data[j];
    &#125;
    PtrL-&gt;Data[i-1]=X;//插入数据
    PtrL-&gt;Last++;//Last仍指向最后一个位置
&#125;
</code></pre>
<h4 id="删除"><a href="#删除" class="headerlink" title="删除"></a>删除</h4><p>（删除第i（1&lt;=i&lt;=n）位置的元素）</p>
<pre><code class="c++">void Delete (int i,List PtrL)&#123;
    //判断i是否合法
    if(i&lt;1 || i &gt; PtrL-&gt;Last+1)&#123;
        cout&lt;&lt;&quot;不存在第&quot;&lt;&lt;i&lt;&lt;&quot;个元素&quot;;
        return;
    &#125;
    //把i-1位置后面的元素向前挪
    for(int j=i;j&lt;PtrL-&gt;Last;j++)&#123;
        PtrL-&gt;Data[j-1]=PtrL-&gt;Data[j];
    &#125;
    PtrL-&gt;Last--;//Last仍指向最后
&#125;
</code></pre>
<h2 id="链式表"><a href="#链式表" class="headerlink" title="链式表"></a>链式表</h2><h3 id="基本原理"><a href="#基本原理" class="headerlink" title="基本原理"></a>基本原理</h3><p>我们需要先创建一个结构体（里面包含一个数据、一个后继指针）</p>
<p>data 用来储存数据，</p>
<p>next 后继指针用来储存下一节点的地址。</p>
<pre><code class="c++">struct node&#123;
   int data;
    node* next;
&#125;;
</code></pre>
<p>我们再创建几个结构体指针 node *head， *p， *q， *t。</p>
<p>head指针：用来储存链表的首地址。</p>
<p>p指针：为临时指针，来储存新建的节点</p>
<p>q指针：储存上一节点的地址</p>
<p>t指针：用来遍历节点</p>
<p><img data-fancybox="gallery" data-sizes="auto" data-src="Snipaste_2021-05-14_20-41-25.png" alt="art" class="lazyload"></p>
<pre><code class="c++">#include &lt;iostream&gt;
using namespace std;


struct node
&#123;
    int data;
    node* next;
&#125;;
int main()
&#123;
    

    node* p, * q, * t, * head;
    head = NULL;            //初始化头指针为空
    q = NULL;
    int n, a;
    cout &lt;&lt; &quot;输入数据个数&quot;;
    cin &gt;&gt; n;
    for (int i = 0; i &lt; n; i++) &#123;
        cin &gt;&gt; a;
        p = (node*)new node;    //申请一个空间,用来存放一个节点，并临时指针p指向该节点
        p-&gt;data = a;            //储存数据在data里
        p-&gt;next = NULL;            //设置当前节点的后继指针指向空，即为链尾
        if (head == NULL) head = p;     //如果头指针为空，则头指针指向p
        else q-&gt; next=p ;                //如果不是第一个节点，则把上一节点的后继指针指向临时指针
        q = p;
    &#125;
    t = head;
    while (t != NULL) &#123;
        cout &lt;&lt; t-&gt;data &lt;&lt; &quot;\t&quot;;
        t = t-&gt;next;
    &#125;
    return 0;
&#125;
</code></pre>
<h3 id="主要操作-1"><a href="#主要操作-1" class="headerlink" title="主要操作"></a>主要操作</h3><h4 id="求表长"><a href="#求表长" class="headerlink" title="求表长"></a>求表长</h4><p>进行一次遍历</p>
<pre><code class="c++">int Length(node* PtrL)
&#123;
    node8 p=PtrL; //p指向头指针
    int j=0;
    while(p!=0)&#123;
        p=p-&gt;next;
        j++;
    &#125;
    return j;
&#125;
</code></pre>
<h4 id="查找-1"><a href="#查找-1" class="headerlink" title="查找"></a>查找</h4><p>（1）按序号查找</p>
<p>输入第k位置，返回k位置的地址</p>
<pre><code class="c++"> node* FindKth(int k,node* head)
 &#123;
     node* p=head;
     int i=1;
     for(p!=NULL &amp;&amp; i&lt;k)
     &#123;
         p=p-&gt;next;
         i++;
     &#125;
     if(i==k) return p;//找到第k个，返回指针
     else return NULL;//没找到
 &#125;
</code></pre>
<p>(2)按值查找</p>
<pre><code class="c++">node *Find(ElementType X,node* head)
&#123;
    node* p=head;
    while(p!=NULL &amp;&amp; p-&gt;Data!=x)
        p=p-&gt;next;
    if(p-&gt;Data==x) return p;//找到
    else return NULL;//没找到
&#125;
</code></pre>
<h4 id="插入-1"><a href="#插入-1" class="headerlink" title="插入"></a>插入</h4><p>插入数据就是让前一个数据的后继指针指向新的节点，新的节点的后继指针指向后一个节点。</p>
<p><img data-fancybox="gallery" data-sizes="auto" data-src="Snipaste_2021-05-14_22-52-16.png" alt="art" class="lazyload"></p>
<pre><code class="c++">//插入在第i-1（1&lt;=i&lt;=n+1)个节点后插入一个值为X的新节点

node *INsert(ElementType X,int i,node* head)
&#123;
    node* p,* s;
    if(i==1)&#123;       //插入点在表头
        s=(node*)new node;
        s-&gt;next=head;
        s-&gt;Data=X;
        return s; //返回新表头指针
    &#125;
    p = FindKth(i-1,head);//查找第i-1节点
    if(p = NULL)&#123;
        cout &lt;&lt; &quot;参数错误&quot;;
        return NULL;
    &#125;
    else&#123;
        s=(node*)new node;//申请新节点
        s-&gt;next=p-&gt;next;//临时指针后继指针指向现在节点的下一个节点
        s-&gt;data=X;
        p-&gt;next=s;//当前节点的后继指针指向临时节点
        return head;//返回头指针
    &#125;
&#125;


</code></pre>
<h4 id="删除-1"><a href="#删除-1" class="headerlink" title="删除"></a>删除</h4><p>(1)找到i-1节点，p指向</p>
<p>(2)指针s指向要被删除的结点，p的下一结点</p>
<p>(3)修改指针，删除s所指向结点</p>
<p>(4)最后释放s所指结点的空间</p>
<pre><code class="c++">node* Delete(int i,node* head)
&#123;
    node* p,* s;
    if(i==1)&#123;
        s=head;
        if(head != NULL)
            head = head-&gt;next;
        else return NULL;
        delete s;
        return head;
    &#125;
    p = FinKth(i-1,head);
    if(p==NULL)&#123;
        cout &lt;&lt; &quot;第&quot; &lt;&lt;i-1 &lt;&lt;&quot;结点不存在&quot;;
    &#125;else if(p-&gt;next==NULL)
        cout&lt;&lt; &quot;第&quot; &lt;&lt; i &lt;&lt;&quot;结点不存在&quot;;
    else &#123;
        s=p-&gt;next;
        p-&gt;next=s-&gt;next;
        delete s;
        return head;
    &#125;
&#125;
</code></pre>
<p>全部代码：</p>
<pre><code class="c++">#include &lt;iostream&gt;
using namespace std;
//定义结构体
struct node
&#123;
    int Data;
    node* next;
&#125;;
//查找函数
node* FindKth(int k, node* head) &#123;
    node* p = head;
    int i = 1;
    while (p != NULL &amp;&amp; i &lt; k) &#123;
        p = p-&gt;next;
        i++;
    &#125;
    if (i == k) return p;
    else return NULL;
&#125;

//删除
node* Delete(int i, node* head)
&#123;
    node* p, *s;
    if (i == 1) &#123;
        s = head;
        if (head != NULL) head = head-&gt;next;
        else return NULL;
        delete s;
        return head;
    &#125;
    p=FindKth(i - 1, head);
    if (p == NULL) &#123;
        cout &lt;&lt; &quot;第&quot; &lt;&lt; i - 1 &lt;&lt; &quot;个元素不存在&quot;;
        return NULL;
    &#125;
    else if (p-&gt;next == NULL) &#123;
        cout &lt;&lt; &quot;第&quot; &lt;&lt; i &lt;&lt; &quot;个元素不存在&quot;;
        return NULL;
    &#125;
    else &#123;
        s = p-&gt;next;
        p-&gt;next = s-&gt;next;
        delete s;
        return head;
    &#125;

&#125;
//插入
node* Insert(int X,int i, node* head)
&#123;
    node* p,* q;
    if (i == 1) &#123;
        p = (node*)new node;
        p-&gt;Data = X;
        p-&gt;next = head;
        return p;
    &#125;
    q = FindKth(i - 1, head);
    if (q == NULL) &#123;
        cout &lt;&lt; &quot;参数错误&quot;;
        return NULL;
    &#125;
    else &#123;
        p = (node*)new node;
        p-&gt;Data = X;
        p-&gt;next = q-&gt;next;
        q-&gt;next = p;
        return head;
    &#125;
&#125;
int main() &#123;
    node* head, * p, * q, * t;
    head = NULL;
    q = NULL;
    int n, a;
    cin &gt;&gt; n;
    for (int i = 0; i &lt; n; i++) &#123;
        cin &gt;&gt; a;
        p = (node*)new node;
        p-&gt;Data = a;
        p-&gt;next = NULL;
        if (head == NULL) &#123;
            head = p;
        &#125;
        else &#123;
            q-&gt;next = p;
        &#125;
        q = p;
    &#125;
    Insert(100, 3, head);
    t = head;
    Delete(2, head);
    while (t != NULL) &#123;
        cout &lt;&lt; t-&gt;Data &lt;&lt; &quot; &quot;;
        t = t-&gt;next;
    &#125;

&#125;
</code></pre>
<h4 id="多重链表"><a href="#多重链表" class="headerlink" title="多重链表"></a>多重链表</h4><p>多重链表：链表中的结点可能同时属于多个链</p>
<p>多重链表中节点的指针域会有多个（但包含两个指针域的链表并不一定是多重链表，比如双向链表）</p>
<p>to be continue …</p>

  </article>

  
    
  <div class="nexmoe-post-copyright">
    <strong>本文作者：</strong>lingqu<br>
    <strong>本文链接：</strong><a href="https://lingqu.github.io/2021/05/16/linearList/" title="https:&#x2F;&#x2F;lingqu.github.io&#x2F;2021&#x2F;05&#x2F;16&#x2F;linearList&#x2F;" target="_blank" rel="noopener">https:&#x2F;&#x2F;lingqu.github.io&#x2F;2021&#x2F;05&#x2F;16&#x2F;linearList&#x2F;</a><br>
    
      <strong>版权声明：</strong>本文采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/cn/deed.zh" target="_blank">CC BY-NC-SA 3.0 CN</a> 协议进行许可
    
  </div>


  
  
  <div class="nexmoe-post-meta nexmoe-rainbow">
    
    
        <a class="nexmoefont icon-tag-fill -none-link" href="/tags/C/" rel="tag">C++</a> <a class="nexmoefont icon-tag-fill -none-link" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag">数据结构</a>
    
</div>

  <div class="nexmoe-post-footer">
    <section class="nexmoe-comment">
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1.5.0/dist/gitalk.min.css">
<div id="gitalk"></div>
<script src="https://cdn.jsdelivr.net/npm/gitalk@1.5.0/dist/gitalk.min.js"></script>
<script type="text/javascript">
    var gitalk = new Gitalk({
        clientID: '80b2453b6d5f37ad6225',
        clientSecret: '43e99fa852795c9a7b3eb924b2558c64b84bbdeb',
        id: window.location.pathname,
        repo: 'nexmoe.github.io',
        owner: 'nexmoe',
        admin: 'nexmoe'
    })
    gitalk.render('gitalk')
</script>
</section>
  </div>
</div>
        <div class="nexmoe-post-right">
          <div class="nexmoe-fixed">
            <div class="nexmoe-tool"> 
              
                
              
              <a href="#nexmoe-content" class="toc-link" aria-label="回到顶部" title="top"><button class="mdui-fab mdui-ripple"><i class="nexmoefont icon-caret-top"></i></button></a>
            </div>
          </div>
        </div>
    </div>
  </div>
  <script src="https://cdn.jsdelivr.net/combine/npm/lazysizes@5.1.0/lazysizes.min.js,gh/highlightjs/cdn-release@9.15.8/build/highlight.min.js,npm/mdui@0.4.3/dist/js/mdui.min.js?v=1"></script>
<script>
	hljs.initHighlightingOnLoad();
</script>

<script src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>


<script src="https://cdn.jsdelivr.net/gh/xtaodada/xtaodada.github.io@0.0.2/copy.js"></script>
 

<script src="/js/app.js?v=1629344957178"></script>

<script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.8.1/dist/js/jquery.justifiedGallery.min.js"></script>
<script>
	$(".justified-gallery").justifiedGallery({
		rowHeight: 160,
		margins: 10,
	});
</script>

  





</body>

</html>
